﻿using LanguageExt;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace leetcode_1
{
    public class Solution
    {
        //两遍哈希表
        //哈希表可以用空间来换取时间，将查找时间从O(n)降低为O(1). 哈希表正是为此目的而构建的，它支持以近似恒定的时间进行快速查找。这里用“近似”来描述，是因为一旦出现冲突，查找用时可能会退化到O(n)。但只要仔细的挑选哈希函数，在哈希表中进行查找的用时应当被摊销为O(1).
        //通过哈希表检查数组中是否存在目标数组，若存在则找出该数组的索引。
        //首先做一个键值为该数组元素、值为该数组索引的字典。此时时间复杂度为O(n)，空间复杂度为O(1)。
        //再次遍历数组，匹配字典中[target-目标元素 = 键值]的值。此时时间复杂度为O(n)，空间复杂度为O(n)
        public int[] TwoSum_TwiceHash(int[] nums, int target)
        {
            if (nums == null || nums.Length == 0) return new int[0];

            Dictionary<int, int> dict = new Dictionary<int, int>();
            for(int n = 0; n < nums.Length; n++)
            {
                //判断是否有重复元素，如果有重复元素匹配target值，则直接输出
                if(dict.ContainsKey(nums[n]))
                {
                    if (nums[n] * 2 == target)
                    {
                        return new int[] { dict[nums[n]], n };
                    }
                }
                else
                {
                    //把数组转换成需要的字典
                    dict.Add(nums[n], n);
                }
            }

            for (int n = 0; n < nums.Length; n++)
            {
                int index = target - nums[n];
                if (dict.ContainsKey(index) && dict[index] != n)
                {
                    return new int[] { n, dict[index] };
                }

            }


            return new int[] {0,0};
        }

        //一遍哈希表
        //一边插入哈希表一遍在哈希表匹配符合[target - 当前元素 = 键值]的值
        public int[] TwoSum_OnceHash(int[] nums, int target)
        {
            if (nums == null || nums.Length == 0) return new int[0];

            Dictionary<int, int> dict = new Dictionary<int, int>();
            for (int n = 0; n < nums.Length; n++)
            {
                int index = target - nums[n];
                if (dict.ContainsKey(index) && dict[index] != n)
                {
                    return new int[] { dict[index], n };
                }
                else
                {
                    dict.Add(nums[n], n);
                }
            }


            return new int[] { 0, 0 };
        }
    }
}
